Булеан

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку
Булеан
Зображення
Досліджується в theory of power setsd і теорія множин
Формула
Підтримується Вікіпроєктом Вікіпедія:Проєкт:Математика
CMNS: Булеан у Вікісховищі
Елементи булеана множини {x,y,z}, зображені в порядку включення елементів

Булеан (англ. power set, нім. potenzmenge) — у теорії множин, це множина всіх підмножин даної множини , позначається або (оскільки вона відповідає множині відображень з в ).

Якщо дві множини мають однакову потужність, то їх булеани теж мають рівну потужність. Обернене твердження (тобто ін'єктивність операції для кардиналів) є незалежним від ZFC.

У категорії множин можна спорядити функцію структурою коваріантного або контраваріантного функтора в такий спосіб:

  • коваріативний функтор відображає функцію у функцію таку, що вона відображає у образ відносно ;
  • контраваріативний функтор відображує функцію в таку, що вона відображає у повний прообраз відносно .

Приклад

[ред. | ред. код]

Нехай . Тоді підмножинами є:

  • (або ) — порожня множина

Отже, булеаном множини є множина , , , , , , , .

Властивості

[ред. | ред. код]

Якщо  — скінченна множина та , то кількість підмножин дорівнює . Цей аспект, який є передумовою до позначення , можна подати так:

Спершу якось упорядкуємо елементи . Ми записуємо кожну підмножину у вигляді , де , може приймати значень 0 або 1. Якщо , тоді  -ий елемент множини належить підмножині; в іншому випадку, цей елемент відсутній. Очевидно, кількість різних підмножин, які можна отримати в такий спосіб, дорівнює .

Діагональний метод Кантора показує, що булеан множини (скінченної або нескінченної) завжди має строго більшу потужність, ніж сама множина . Зокрема, теорема Кантора свідчить, що булеан зліченної множини є незліченним. Наприклад, можна утворити бієктивне відображення між булеаном множини натуральних чисел та множиною дійсних чисел.

Булеан множини , поряд з операціями об'єднання, перетину та доповнення, можна розглядати як приклад булевої алгебри. Можна показати, що будь-яка скінченна булева алгебра є ізоморфною до булевої алгебри булеана скінченної множини. Для нескінченних булевих алгебр ця умова не виконується, але будь-яку нескінченну булеву алгебру можна подати як підалгебру булеана булевої алгебри (див.: теорема Стоуна про представлення булевих алгебр).

Булеан множини формує абелеву групу за операцією симетричної різниці та комутативний моноїд за операцією перетину. Отже, можна показати (доводячи дистрибутивність), що булеан формує булеве кільце за цими операціями.

Подання підмножин як функцій

[ред. | ред. код]

У теорії множин, позначає множину всіх функцій із в .  — множина всіх відображень із у . Визначаючи функцію в з відповідним прообразом 1, ми бачимо, що відображення між та є бієктивним, де кожна функція є характеристичною функцією підмножини , у якій вона визначена. Таким чином, та можна вважати теоретико-множинно ідентичними.

Це поняття можна застосувати до наведеного вище прикладу, де , щоб побачити ізоморфізм з двійковими числами від 0 до , де  — кількість елементів у множині. У «1» на позиції, яка відповідає позиції елемента у множині, позначає присутність цього елемента. Такими чином, .

Для всієї множини отримуємо:

Алгоритми

[ред. | ред. код]

Для скінченної множини існує рекурсивний алгоритм для знаходження .

Визначимо операцію .

  • Якщо , тоді повернемо .
  • В іншому випадку:
    • Нехай  — будь-який одиничний елемент з .
    • Нехай , де  — відносне доповнення в .
    • Повернемо .

Зв'язок з біномом Ньютона

[ред. | ред. код]

Булеан тісно пов'язаний з біномом Ньютона. Кількість підмножин потужності в булеані множини, потужність якої , є кількістю комбінацій , яку також називають біноміальним коефіцієнтом.

Наприклад, множина із трьох елементів містить:

  • підмножину з 0 елементами (порожня множина);
  • підмножини з 1 елементом (одиничні підмножини);
  • підмножини з 2 елементами (усі можливі пари одиничних підмножин);
  • підмножину з 3 елементами (уся початкова множина).

Підмножини обмеженої потужності

[ред. | ред. код]

Множину підмножин , потужність яких менша ніж , позначають або . Таким чином, множину непорожніх підмножин можна позначити .

Потужність скінченного булеана

[ред. | ред. код]

Справедливе таке твердження: число підмножин скінченної множини, яка складається з елементів, дорівнює . Результат доводиться методом математичної індукції. В разі порожньої множини () тільки одна підмножина — вона сама, і . На кроці індукції твердження вважають встановленим для множин потужності та розглядається довільна множина з кардинальним числом ; зафіксувавши деякий елемент , підмножини множини розділяють на два сімейства:

  1. , що містить ,
  2. , що не містить , тобто є підмножинами множини .

Підмножин другого типу, за припущенням індукції, , підмножин першого типу рівно стільки ж, оскільки підмножина такого типу отримується з деякої єдиної підмножини другого типу доданням елемента і, отже:

та .

За індукційним припущенням та , тобто:

Див. також

[ред. | ред. код]

Посилання

[ред. | ред. код]